#pragma once
#include <iostream>
namespace mySearchTree
{

    template <class T>
    struct Node
    {
    public:
        Node(const T& data)
            : _data(data)
            , _left(nullptr)
            , _right(nullptr)
        {}
    public:
        T _data;
        Node<T>* _left;
        Node<T>* _right;
    };

    template <class T>
    class serachTree
    {
    public:
        using node = Node<T>;
    public:
        serachTree()
            : _root(nullptr)
            , _size(0)
        {}

        ~serachTree()
        {}

        void insert(const T& data)
        {
            node* new_node = new node(data);
            // 第一次插入
            if(_root == nullptr)
            {
                _root = new_node;
                return ;
            }

            // 第n次（n ≥ 1）插入
            node* cur = _root;
            node* parent = nullptr;

            while(cur)
            {
                parent = cur;
                if(cur->_data > data) cur = cur->_left;
                else                  cur = cur->_right;
            }
            
            if(parent->_data > data) parent->_left = new_node;
            else                     parent->_right = new_node;

            ++_size;
        }

        bool erase(const T& data)
        {
            // 没有结点
            if(_root == nullptr)  return false;
            // 有结点
            node* cur = _root;
            node* parent = nullptr;
            while(cur)
            {   
                parent = cur;
                if(cur->_data > data)       cur = cur->_left;
                else if(cur->_data < data)  cur = cur->_right;
                else
                {
                    // cur 没有左右孩子，可以直接删除
                    if(cur->_left == nullptr && cur->_right == nullptr)
                    {
                        if(parent->_data > data) parent->_left = nullptr;
                        else                     parent->_right = nullptr;
                        delete cur;
                        cur = nullptr;

                        if(_root->_data == data)
                        {
                            _root = nullptr;
                        }
                    }
                    // cur 只有一个孩子
                    else if((cur->_left && cur->_right == nullptr) || (cur->_left == nullptr && cur->_right))
                    {
                        // cur 只有左孩子
                        if(cur->_left)
                        {
                            if(parent->_data > data) parent->_left = cur->_left;
                            else                     parent->_right = cur->_left;
                            delete cur;
                            cur = nullptr;
                        }
                        // cur 只有右孩子
                        else
                        {
                            if(parent->_data > data) parent->_left = cur->_right;
                            else                     parent->_right = cur->_right;
                            delete cur;
                            cur = nullptr;
                        }

                        if(_root->_data = data)
                        {
                            _root = parent;
                        }
                    }
                    // cur 有左右孩子结点，删除当前结点，将左子树最右结点 / 右子树最左节点 换到当前结点
                    else
                    {
                        // 找左子树最右节点
                        node* LTright = cur->_left;
                        node* parent = nullptr;
                        while(LTright->_right)
                        {
                            parent = LTright;+
                            LTright = LTright->_right;
                        }

                        // 最右结点有左子树
                        if(LTright->_left)
                        {
                            if(cur != parent)
                            {
                                cur->_data = parent->_data;
                                cur->_left = LTright;
                                delete parent;
                                parent = nullptr;
                            }
                            else
                            {
                                cur->_data = LTright->_data;
                                cur->_left = LTright->_left;
                                delete LTright;
                                LTright = nullptr;
                            }
                        }
                        // 最右结点没左子树
                        else
                        {
                            cur->_data = LTright->_data;
                            parent->_right = nullptr;
                            delete LTright;
                            LTright = nullptr;
                        }

                        if(_root->_data == data)
                        {
                            _root = cur;
                        }
                    }
                    
                    --_size;
                    return true;
                }
            }
            return false;
        }

        bool find(const T& data)
        {
            node* cur = _root;
            while(cur)
            {
                if(cur->_data > data)       cur = cur->_left;
                else if(cur->_data < data)  cur = cur->_right;
                else                        return true;
            }
            return false;
        }

        size_t size() {return _size;}
    private:
        node* _root;
        size_t _size;
    };

}